/*
 * @lc app=leetcode.cn id=34 lang=javascript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 *
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 *
 * algorithms
 * Medium (37.20%)
 * Likes:    179
 * Dislikes: 0
 * Total Accepted:    28.3K
 * Total Submissions: 75.8K
 * Testcase Example:  '[5,7,7,8,8,10]\n8'
 *
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * 
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * 
 * 示例 1:
 * 
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 
 * 示例 2:
 * 
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 * 
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// 解法1
// var searchRange = function(nums, target) {
//   let l = 0, r = nums.length - 1, mid = -1
//   while (l <= r) {
//     mid = Math.floor((l + r) / 2)
//     if (nums[mid] > target) r = mid - 1
//     else if (nums[mid] < target) l = mid + 1
//     else {
//       break
//     }
//   }
//   if (mid === -1 || nums[mid] !== target) return [-1, -1]
//   let ll = mid, rr = mid
//   while (ll >= 0 && nums[ll] === target) ll-=1 
//   while (rr < nums.length && nums[rr] === target) rr+=1
//   return [ll + 1, rr - 1]
// };

// 解法2
var searchRange = function (nums, target) {
    let re = [-1, -1]
    let l = findIndex(nums, target, true)
    if (l === nums.length || nums[l] !== target) return re

    re[0] = l
    re[1] = findIndex(nums, target, false) - 1

    return re
};

// 引入参数left, 如果left为true, 那么当中间值与目标值相等时, 不终止查询, 而是继续调整右索引
function findIndex(nums, target, left) {
    let l = 0, r = nums.length
    while (l < r) {
        let mid = Math.floor((l + r) / 2)
        if (nums[mid] > target || (left && nums[mid] === target)) r = mid
        else l = mid + 1
    }
    return l
}

var searchRange1 = function (nums, target) {
    const find = function (arr, k) {
        let i = 0, j = arr.length - 1
        while (i <= j) {
            let mid = (i + j) >> 1
            if (nums[mid] === k) return mid
            else if (nums[mid] > k) {
                j = mid - 1
            }
            else if (nums[mid] < k) {
                i = mid + 1
            }
        }
        return -1
    }
    let p = find(nums, target)
    let ans = [p, p]
    if (p == -1) return ans
    let i = p, j = p
    while (i >= 0 && nums[i] == nums[p]) i -= 1
    while (j >= 0 && nums[j] == nums[p]) j += 1
    return [i + 1, j - 1]
};

let re = searchRange([3, 3, 4], 3)
console.log(re)


// @lc code=end

